1. Field
The present invention relates to techniques for managing an ordered sequence of secrets in limited space in such a way that, at any time, items can be efficiently deleted from the beginning of the sequence, all items in the sequence later than the earliest saved secret can be efficiently computed, and items earlier than the earliest saved secret are infeasible to compute.
2. Related Art
In order to protect sensitive data from unauthorized access, organizations commonly store sensitive data in encrypted form. If the encrypted data needs to be accessed, it must be decrypted using a decryption key. However, such decryption keys can, over time, be obtained by an adversary through compromise or coercion. To remedy this problem, keys can be stored in tamper-resistant smart cards, in which case it is not feasible to covertly discover the keys.
However, smart cards have limited storage space, which makes it impractical (if not impossible) to store a large number of keys on the smart card. Additionally, smart cards have very limited computational speed, which makes it impractical to perform a large number of computations to compute a given secret. These restrictions significantly limit the capabilities of a system that uses a smart card to manage keys.
One technique for achieving the effect of storing a large number of sequential keys (secrets) with limited storage, such that deleted keys cannot be recovered, is to use a hash chain. (Note that we use the terms “key” and “secret” interchangeably throughout this specification.) A traditional cryptographic hash chain is one in which each member of the hash chain is derivable from the previous member. So starting from an initial value, x, the next member is h(x), and the next is h(h(x)), and so on. This technique requires n consecutive applications of the function h to get to the n+1st value.
Using a traditional hash chain, the smart card could store just a single secret, but then it is prohibitively slow to compute a secret n units into the future, because that would require, through traditional techniques, n iterations of the hash function.
Another technique for achieving the effect of storing a large number of secrets with limited storage, such that deleted keys cannot be recovered, is described in patent application Ser. No. 11/405,980, entitled “Method and Apparatus for Securely Forgetting Secrets” by inventors Radia J. Perlman and Anton B. Rang filed on 17 Apr. 2006. In this technique, two secrets are maintained at any time on the smart card. These secrets include: a “current secret,” Si and a “next secret,” Si. A set of other secrets can be stored outside the card, encrypted with Si. Any of the externally stored secrets can be accessed by retrieving it from external storage and decrypting with Si. To delete one of the externally stored secrets, the card retrieves each externally stored secret in turn, decrypts it with Si, encrypts it with Si+1, and stores the result externally from the card. After re-encrypting every one of the externally stored secrets (except the ones to be deleted), the smart card destroys Si. (Note that if the card can only remember one secret at a time, Si+1 can be a one-way hash of Si). This technique is efficient for accessing future secrets, but unfortunately, is slow to delete a secret, because the entire database of secrets must be accessed, decrypted, and then re-encrypted.
Hence, what is needed is a method and an apparatus that can maintain a large number of sequential secrets with relatively small storage and computational ability, such that items can be efficiently and irrevocably deleted from the beginning of the sequence, and any item later in the sequence can be efficiently accessed.